Relations

What is a Relation?

Let $A$, and $B$ be sets. A relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A \times B$. Given an ordered pair $(a,b) \in A \times B$, we say that ”$a$ is related to $b$ by $R$” if and only if $(a,b) \in \mathrel{R}$. We denote this by $a \mathrel{R} b$. We refer to $A$ as the domain of the relation, and to $B$ as the codomain of the relation.

Formally, a relation defined like so is called a binary relation as there are two sets involved. More generally, an $n$-ary relation on sets $A_1, A_2, \ldots, A_n$ is a subset of the Cartesian product $A_1 \times A_2 \times \cdots \times A_n$.

Examples

Simple Explicit Given Relation

We can explicit relation by specifying the pairs that belong to it.

Let $A = \{1, 2, 3\}$ and $B = \{1, 2, 3\}$.

The Cartesian product $A \times B$ is then given by $\{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\}.$

Let’s define a relation $\mathrel{R}$ from $A$ to $B$ as follows: $\mathrel{R} = \{(1,2), (2,3), (3,1)\}.$

In this case, we can say that:

• $1 \mathrel{R} 2$ (1 is related to 2 by R)
• $2 \mathrel{R} 3$ (2 is related to 3 by R)
• $3 \mathrel{R} 1$ (3 is related to 1 by R)

Since those pairs are in the relation $R$.

And we can say that:

• $1 \not\mathrel{R} 1$
• $1 \not\mathrel{R} 3$
• $2 \not\mathrel{R} 1$
• $2 \not\mathrel{R} 2$
• $3 \not\mathrel{R} 2$
• $3 \not\mathrel{R} 3$

Since those pairs are not in the relation $R$.

Relation Defined by a Condition

We can also define a relation using a specific condition. Let’s define a relation on $\mathbb{Z}$ where two integers are related if they share a common prime factor.

Let $R$ be a relation on $\mathbb{Z}$ defined as follows: for any integers $a$ and $b$, $a \mathrel{R} b$ if and only if there exists a prime integer $k > 1$ such that $k$ divides both $a$ and $b$.

We can say that:

• $6 \mathrel{R} 9$ because both 6 and 9 are divisible by the prime number 3.
• $10 \mathrel{R} 15$ because both 10 and 15 are divisible by the prime number 5.
• $8 \not\mathrel{R} 9$ because there is no prime number that divides both 8 and 9.

Relations on Single Set

When a relation is defined on a single set, it is often referred to as a relation on that set. We simply consider the relation as a subset of the Cartesian product of the set with itself. We could have defined Example 1 as a relation on set $A$ instead of from $A$ to $B$ since both sets are the same.

Inverse Relations

Given a relation $\mathrel{R}$ from set $A$ to set $B$, the inverse relation of $\mathrel{R}$, denoted by $\mathrel{R}^{-1}$, is a relation from set $B$ to set $A$ defined as follows:

$\mathrel{R}^{-1} = \{(b,a) \in B \times A \mid (a,b) \in \mathrel{R}\}.$

Examples

Divisibility Relations

Let $\mathrel{R}$ be a relation on the set of positive integers $\mathbb{Z}^+$ defined by $a \mathrel{R} b$ if and only if $a$ divides $b$ (denoted as $a \mid b$).

Some of the pairs in this relation are: $\{(1,1), (1,2), (1,3), (2,2), (2,4), (3,6), (4,8), \ldots\}.$

The inverse relation $\mathrel{R}^{-1}$ would then be defined by $b \mathrel{R}^{-1} a$ if and only if $a$ divides $b$, that is, $b$ is divisible by $a$. Some of the pairs in this inverse relation are: $\{(1,1), (2,1), (3,1), (2,2), (4,2), (6,3), (8,4), \ldots\}.$

Graphs for Relations

A relation can be visually represented using a directed graph or a bipartite graph.

In a directed graph, each element of the sets involved in the relation is represented as a vertex, and a directed edge is drawn from vertex $a$ to vertex $b$ if $a \mathrel{R} b$.

In a bipartite graph, the vertices are divided into two disjoint sets, one for each set involved in the relation. An edge is drawn between vertex $a$ in the first set and vertex $b$ in the second set if $a \mathrel{R} b$.

Properties of Relations: Reflexivity, Symmetry, and Transitivity

Relations can have various properties. We will discuss three important properties: reflexivity, symmetry, and transitivity in this section.

Reflexivity

A relation $\mathrel{R}$ on a set $A$ is said to be reflexive if every element in $A$ is related to itself. That is, for all $a \in A$, we have $a \mathrel{R} a$.

Symmetry

A relation $\mathrel{R}$ on a set $A$ is symmetric if for all $a,b \in A$, if $a \mathrel{R} b$, then $b \mathrel{R} a$.

Transitivity

A relation $\mathrel{R}$ on a set $A$ is transitive if for all $a,b,c \in A$, if $a \mathrel{R} b$ and $b \mathrel{R} c$, then $a \mathrel{R} c$.

Please note the conditional nature of Transitivity. The property states if both $a \mathrel{R} b$ and $b \mathrel{R} c$, then $a \mathrel{R} c$. That is, the every combination of the cartesian product need not be in the relation. The statement is vacously true if either $a \mathrel{R} b$ or $b \mathrel{R} c$ is false.

Transitive Closure

We can find the transititive closure of a relation by adding the minimum number of pairs to make it transitive. For example, if we have a relation $\mathrel{R} = \{(1,2), (2,3)\}$, we can add the pair $(1,3)$ to make it transitive. The transitive closure of $\mathrel{R}$ would then be $\{(1,2), (2,3), (1,3)\}$.

Equivalence Relations & Partitions

The partition of a set is a way of dividing the set into non-overlapping subsets such that every element in the original set is included in exactly one subsets.

Provided the relation has been partitioned into these subsets, we can define an equivalence relation based on this partition. We say that two elements are related if they belong to the same subset in the partition. This relation will be always be reflexive, symmetric, and transitive, and forms an equivalence relation.

An equivalence relation is a relation that is reflexive, symmetric, and transitive.

Equivalence Classes

Suppose that there is an equivalace reation on a set $A$. If $a$ is any particular element of $A$, then the equivalence class of $a$ is the subset of $A$ consisting of all elements that are related to $a$ by the equivalence relation. We denote the equivalence class of $a$ by $[a]$.

Formally, the equivalence class of $a$ is defined as follows: $[a] = \{ x \in A \mid x \mathrel{R} a \}$

Partial Orders

Let $R$ be a relation on a set $A$. The relation $R$ is called a partial order if it is reflexive, antisymmetric, and transitive.

We say that a relation $R$ is antisymmetric if for all $a,b \in A$, if $a \mathrel{R} b$ and $b \mathrel{R} a$, then $a = b$.

We can say that a relation is not antisymmetric if we negate our definition of antisymmetry. If $a \neq b$, then if $a \mathrel{R} b$, it must be that $b \not\mathrel{R} a$.

Hasse Diagrams

We can create a Hasse diagram for a partially ordered relation. A Hasse diagram is a graphical representation of a finite partially ordered set, where the elements are represented as vertices and the order relations are represented as edges. In a Hasse diagram, we omit the edges that can be inferred by transitivity and we arrange the vertices such that if $a \mathrel{R} b$, then vertex $a$ is placed lower than vertex $b$.

Starting with the directed graph of the relation, we can create the Hasse diagram by removing self-loops (to account for reflexivity), removing edges that can be inferred by transitivity, and arranging the vertices vertically according to the order relation.

Partially and Totally Ordered Sets

Suppose we have a partially order relation on a set $A$. We say a pair of elements are comparable if either $a \mathrel{R} b$ or $b \mathrel{R} a$. If every pair of elements in the set are comparable, then we say that the partially ordered set is a total order relation (or linear order).

Let $A$ be a set that is partially ordered by relation $R$. A subset $B \subseteq A$ is called a chain if every pair of elements in $B$ are comparable. A subset $C \subseteq A$ is called an antichain if no two distinct elements in $C$ are comparable. The length of this chain will be one less than the number of elements in the chain since the length is defined by the number of edges connecting the elements.

Maximal, Minimal Elements, Greatest, and Least Elements

An element $m \in A$ is called a maximal element if there is no element $a \in A$ such that $m \mathrel{R} a$ and $m \neq a$. Similarly, an element $n \in A$ is called a minimal element if there is no element $a \in A$ such that $a \mathrel{R} n$ and $n \neq a$.

An element $g \in A$ is called the greatest element if for all $a \in A$, we have $a \mathrel{R} g$. Similarly, an element $l \in A$ is called the least element if for all $a \in A$, we have $l \mathrel{R} a$.

An element can be both maximal and greatest, or minimal and least, but not necessarily. A set can have multiple maximal or minimal elements, but at most one greatest or least element.

One can quickly use a Hasse diagram to identify maximal, minimal, greatest, and least elements. Maximal elements are those at the top of the diagram with no edges going upwards, while minimal elements are at the bottom with no edges going downwards. The greatest element, if it exists, is the single element at the very top of the diagram, and the least element, if it exists, is the single element at the very bottom.